// https://leetcode.cn/problems/last-substring-in-lexicographical-order/
// Created by ade on 2022/8/3.
//
#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    // 暴力法会超时
    string lastSubstring1(string s) {
        int len = s.size();
        char maxChar = s[len - 1];
        int prev = len - 1;
        int maxIndex = len - 1;
        for (int i = len - 1; i >= 0; i--) {
            if (maxChar < s[i]) {
                maxIndex = i;
                maxChar = s[i];
            } else if (maxChar == s[i]) {
                while (i > 0 && s[i] == s[i - 1]) {
                    i--;
                }
                int minLen = min(len - maxIndex, maxIndex - i);
                if (s.substr(i, minLen).compare(s.substr(maxIndex, minLen)) > 0) {
                    maxIndex = i;
                }
            }
        }
        return s.substr(maxIndex);
    }

    // 双指针思路：l左侧起点 r右侧
    /*
     * 1.如果 l < r 则 l = r, r++;
     * 2.如果 l > r 则 l不变 r++;
     * 3.如果 l == r,循环比较l后面和r后面的字符，直到比较出大小
     *          如果l侧小于r侧， l = r; r++
     *          如果l侧大于r侧， l不变，r = r+比较长度的大小
     * */

    string lastSubstring(string s) {
        /*int l = 0, r = 1, k = 0, n = s.size();
        while(r + k < n){
            if(s[l + k] == s[r + k]) k++;
            else if(s[l] < s[r + k]){
                l = r + k;
                r = l + 1;
                k = 0;
            }
            else if(s[l + k] < s[r + k]){
                l = r;
                r++;
                k = 0;
            }
            else{
                r++;
                k = 0;
            }
        }
        return s.substr(l);*/

        // cacacacacacac
        int len = s.size();
        int left = 0, right = 1, k = 0;
        while (right + k < len) {
            if (s[left + k] == s[right + k]) {
                k++;
                continue;
            }

            if (s[left] < s[right + k]) {
                // 如果left的字符小于最右侧的字符，优先处理
                left = right + k;
                right = left + 1;
                k = 0;
            } else if (s[left + k] < s[right + k]) {
                // 左侧最后一个字符小于右侧最后一个字符
                left = right;
                right++;
                k = 0;
            }else{
                right++;
                k = 0;
            }
        }
        return s.substr(left);
    }
};

int main() {
    Solution so;
    // cbacbacbacbacbacbacb
    cout << so.lastSubstring("abab");
    return 0;
}